#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/12
# @Author   :Changshu
# @File     :Exercise_563.py

# 563. 二叉树的坡度
# 给定一个二叉树，计算 整个树 的坡度 。
#
# 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
#
# 整个树 的坡度就是其所有节点的坡度之和

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

'''深度优先递归，时间复杂度O(n) 空间复杂度O(n)'''
class Solution:
	tilt=0
	def findTilt(self, root: TreeNode) -> int:
		def tranverse(root:TreeNode):
			if not root:
				return 0
			left=tranverse(root.left)
			right=tranverse(root.right)
			self.tilt+=abs(left-right)
			return left+right+root.val
		tranverse(root)
		return self.tilt

if __name__ == '__main__':
	root=TreeNode(4)
	node2_1=TreeNode(2)
	node2_2 = TreeNode(9)
	node3_1 = TreeNode(3)
	node3_2 = TreeNode(5)
	node3_3 = TreeNode(7)

	root.left=node2_1
	root.right = node2_2
	node2_1.left=node3_1
	node2_1.right = node3_2
	node2_2.right=node3_3

	solution=Solution()
	print(solution.findTilt(root))